package com.imooc.study.imoocstudy.datastructure.sortalgorithm;

import java.util.Arrays;

/**
 * 插入排序：
 * 空间复杂度：O(1)
 * 时间复杂度：O(n^2)
 */
public class InsertionSortTest {

    public static void insertionSort(int[] arrs){

        //1.循环购买玩具：模拟玩具的增加过程
        for (int i = 0; i < arrs.length; i ++){

            // 2.对自己的玩具进行排序
            for (int j=i-1; j >=0;j --){

                // 3.对玩具进行喜爱程度（数字大小）选择；
                if (arrs[j] > arrs[j+1]){
                    // 交换数据
                    int temp = arrs[j];
                    arrs[j] = arrs[j+1];
                    arrs[j+1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] a = new int[]{10,8,100,78,66,33,88};

        InsertionSortTest.insertionSort(a);

        Arrays.stream(a).forEach(System.out::println);
    }
}
